package stackqueue;

import org.junit.jupiter.api.Test;

import java.util.Stack;

/**
 * 使用栈结构实现队列
 */
public class StackToQueue {

    @Test
    public void stackToQueue() {
        MyStackToQueue stack = new MyStackToQueue();
        stack.add(1);
        stack.add(2);
        stack.add(3);
        stack.add(4);
        stack.add(5);

        System.out.println(stack.poll());
        System.out.println(stack.poll());
        System.out.println(stack.poll());
        System.out.println(stack.poll());
        System.out.println(stack.poll());

        stack.add(6);
        System.out.println(stack.poll());
    }

    /**
     * 自定义队列结构
     * 思想：使用两个栈结构实现，第一个栈在添加数据时进行数据保存，第二个栈在取数据从第一个栈中倒序获取数据，然后存放进去，在弹出返回。
     */
    static class MyStackToQueue {

        // 第一个栈用来保存原始数据
        Stack<Integer> stack1 = new Stack<>();
        // 第二个栈用来倒序保存第一个栈中的数据，利用栈的先进后出的特点，实现队列。
        Stack<Integer> stack2 = new Stack<>();

        public synchronized boolean add(Integer data) {
            // 倒序保存数据的栈不为空，不能添加数据，否则就会破坏数据顺序
            if (!stack2.isEmpty()) {
                System.out.println("暂时不能添加数据");
                return false;
            }
            // 第一个栈用来保存原始数据
            return stack1.add(data);
        }

        public synchronized Integer poll() {
            if (stack2.isEmpty()) {
                // 第二个栈用来倒序保存第一个栈中的数据，利用栈的先进后出的特点，实现队列。
                for (int i = stack1.size() - 1; i >= 0; i--) {
                    stack2.add(stack1.pop());
                }
            }
            // 第一个栈先进的数据存放在了栈顶，弹出时，先弹出栈顶数据，相当于队列的先进先出
            return stack2.pop();
        }
    }
}
